package 动态规划;

/**
 * @author TTDB
 * @create 2025/9/23
 */
public class coinChange {

        int[] memo;
        public int coinChange(int[] coins, int amount) {
            if(coins.length == 0){
                return -1;
            }
            memo = new int[amount];

            return findWay(coins,amount);
        }
        // memo[n] 表示钱币n可以被换取的最少的硬币数，不能换取就为-1
        // findWay函数的目的是为了找到 amount数量的零钱可以兑换的最少硬币数量，返回其值int
        public int findWay(int[] coins,int amount){
            if(amount < 0){
                return -1;
            }
            if(amount == 0){
                return 0;
            }
            // 记忆化的处理，memo[n]用赋予了值，就不用继续下面的循环
            // 直接的返回memo[n] 的最优值
            if(memo[amount-1] != 0){
                return memo[amount-1];
            }
            int min = Integer.MAX_VALUE;
            for(int i = 0;i < coins.length;i++){
                int res = findWay(coins,amount-coins[i]);
                if(res >= 0 && res < min){
                    min = res + 1; // 加1，是为了加上得到res结果的那个步骤中，兑换的一个硬币
                }
            }
            memo[amount-1] = (min == Integer.MAX_VALUE ? -1 : min);
            return memo[amount-1];
        }


        public int coinChange2(int[] coins, int amount) {
            // 自底向上的动态规划
            if(coins.length == 0){
                return -1;
            }

            // memo[n]的值： 表示的凑成总金额为n所需的最少的硬币个数
            int[] memo = new int[amount+1];
            memo[0] = 0;
            for(int i = 1; i <= amount;i++){
                int min = Integer.MAX_VALUE;
                for(int j = 0; j < coins.length; j++){
                    if(i - coins[j] >= 0 && memo[i-coins[j]] != Integer.MAX_VALUE){
                        min = Math.min(min, memo[i-coins[j]] + 1);
                    }
                }
                // memo[i] = (min == Integer.MAX_VALUE ? Integer.MAX_VALUE : min);
                memo[i] = min;
            }

            return memo[amount] == Integer.MAX_VALUE ? -1 : memo[amount];
        }
}
